Programmable logic devices (PLDs) exist as a well-known type of integrated circuit (IC) that may be programmed by a user to perform specified logic functions. There are different types of programmable logic devices, such as programmable logic arrays (PLAs) and complex programmable logic devices (CPLDs). One type of programmable logic device, called a field programmable gate array (FPGA), is very popular because of a superior combination of capacity, flexibility, time-to-market, and cost.
An FPGA typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a hierarchy of programmable routing resources, which are comprised of metal wire segments and programmable routing switches, also referred to as programmable interconnection points (PIPs). These CLBs, IOBs, and programmable routing resources are customized by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and programmable routing resources are configured. The configuration bitstream may be read from an external memory, conventionally an external integrated circuit memory EEPROM, EPROM, PROM, and the like, though other types of memory may be used. The collective states of the individual memory cells then determine the function of the FPGA.
State-of-the art FPGAs contain tens of thousands of CLBs. For such devices, the task of establishing the required interconnections between the primitive cells inside a CLB and between the CLBs themselves becomes so onerous that it can only be accomplished with the assistance of computer-aided design tools. Accordingly, the manufacturers of FPGAs have developed place and route software tools which may be used by end customers to implement their respective designs in their FPGAS.
During the placement phase, primitive cells within the FPGA are assigned physical positions on the chip. In the routing phase, a suitable path between components that are to be connected is established using wires and switches. Finding the optimum routing solution within an FPGA is “non-polynomial-hard” or “NP-hard”. Notably, some routing algorithms that are used to route signals within a programmable logic device, such as an FPGA, employ a “routing graph” to model the programmable routing resources. For example, a widely used algorithm used for routing signals using a routing graph is a variant form of the well-known maze router. A routing graph contains a set of nodes and directed edges. The nodes in the routing graph represent conductors in the programmable logic device. Edges are present between nodes corresponding to conductors that can be electrically connected to one another. For example, in FPGA devices, edges are present between nodes corresponding to conductors that may be connected to each other through a programmable routing switch.
A signal in a design is a set of pins that must be connected together electrically. A signal is generally comprised of a source pin and one or more load pins. The pins on a signal correspond to specific nodes in the routing graph. To route a signal, the router identifies paths between the signal's pin nodes in the routing graph such that all the pins of the signal are connected together. For example, the maze router algorithm searches for a path between a signal source pin and load pins by performing a breadth first search on the routing graph.
Conventionally, a routing graph includes a node for each conductor and an edge for each pair of conductors that may be electrically connected through a PIP. Such a routing graph is referred to herein as a “detailed routing graph”. A detailed routing graph that models the programmable interconnect of an FPGA may include millions of nodes and even more edges between nodes. As such, routing a signal using a detailed routing graph may become particularly onerous and time-consuming.
Accordingly, there exists a need in the art for a signal routing mechanism that overcomes the complexities associated with the use of a detailed routing graph.